Programación Avanzada

1 Contenido de la clase

La función 91 de John McCarthy (1970) Pág. 118

La función 91 está definida así:

f(x) = x − 10  si  x > 100
f(x) = f( f( x + 11 ) )  si  x ≤ 100

Se pide demostrar que la función obtiene f(x) = 91 para todo entero x ≤ 100 y f(x) = x − 10 para x > 100.

Sobre John Patrick McCarthy (4 de septiembre de 1927 – 24 de octubre de 2011, 84 años): es el padre de la Inteligencia Artificial (1956, conferencia de Dartmouth, Hanover, Nuevo Hampshire, EE. UU.), creó el lenguaje Lisp y recibió el Premio Turing en 1971.

La conferencia referencia el proyecto Funcion91JohnMcCarthy de Visual Studio y la demostración se hace por inducción.

Demostración por inducción Pág. 119-120

Sea P(x) la proposición: "la función obtiene f(x) = 91 para todo entero x ≤ 100 y f(x) = x − 10 para x > 100". Se prueba por inducción con k = 1:

• Paso base (x = 1): se encadena la definición: f(1) = f(f(12)), f(f(f(23))), f(f(f(f(34)))), … hasta llegar a valores mayores que 100.
• Hipótesis de inducción: suponer que P(x) es verdadera para alguna x ≥ 1.
• Paso inductivo: demostrar que P(x + 1) es cierto (es decir, f(x+1) = 91 para x+1 ≤ 100 y f(x+1) = (x+1) − 10 para x+1 > 100).

El principio de inducción modificado (inducción fuerte) Pág. 121

Sea k un entero fijo (positivo, negativo o cero). Para cada entero n ≥ k se tiene una proposición P(n) y se desea demostrar que P(n) es verdadera para todas las n ≥ k:

• P(k) es verdadera (paso básico o paso base).
• Si para n ≥ k se sigue que P(n) es verdadera (paso inductivo) cuando P(m) es verdadera para n < m < k (hipótesis de inducción).
• Entonces el principio de inducción matemática establece que P(n) es verdadera para toda n ≥ k.

La diferencia con la inducción simple: aquí la hipótesis usa los valores de P(m) con m entre n y k, lo que permite demostrar casos que dependen de valores mayores (como x + 11 en la función 91).

Demostración de la función 91 con el principio modificado Pág. 122-125

Si x > 100, entonces f(x) = x − 10 por definición.

• Paso base (k = 100): demostrar el enunciado para k = 100: f(100) = f(f(111)) = f(101) = 91.
• Paso inductivo: supongamos que x < k = 100 y que la hipótesis de inducción es cierta para m ≥ x. P. D. f(x) = 91 para x < 100. Como x < 100, f(x) = f(f(x + 11)). Hay dos casos:
  • a) x + 11 > 100. Entonces f(x) = f(f(x + 11)) = f((x + 11) − 10) = f(x + 1) = 91, porque por hipótesis de inducción f(m) = 91 para m ≥ x y x + 1 > x.
  • b) x + 11 ≤ 100. Entonces f(x) = f(f(x + 11)) = f(91), porque por hipótesis f(m) = 91 para m ≥ x y x + 11 > x. Y f(91) = 91, porque x + 11 ≤ 100 implica x ≤ 89 < 91, así que 91 está en el intervalo demostrado (y por hipótesis f(m) = 91 para m ≥ x con 91 > x).

Por el principio de inducción, la proposición P(x) es cierta: f(x) = 91 para todo entero x ≤ 100 y f(x) = x − 10 para x > 100.

La función de Ackermann. Otras aplicaciones de la inducción Pág. 126

En 1928, Wilhelm Friedrich Ackermann (nació el 29 de marzo de 1896 en Herscheid, Alemania; murió el 24 de diciembre de 1962 en Ludenscheid, Alemania) encontró una función doblemente recursiva de tres variables A(m, n, p) (notación m → n → p) que crece muy rápidamente:

A(m, n) = n + 1  si  m = 0
A(m, n) = A(m – 1, 1)  si  m > 0 y n = 0
A(m, n) = A(m – 1, A(m, n – 1))  si  m y n > 0

O bien la definición alternativa:

A(0, y) = y + 1  … (1)
A(x + 1, 0) = A(x, 1)  … (2)
A(x + 1, y + 1) = A(x, A(x + 1, y))  … (3)

La conferencia plantea: ¿qué valor devuelve la función? ¿por qué para valores pequeños se obtienen valores muy grandes? ¿por qué para valores aún pequeños el programa envía un error de StackOverflowException? Y refiere los proyectos Ackermann en Visual Studio, el programa Ackermann en Haskell y el documento Ackermann.doc.

Algunas propiedades de la función de Ackermann Pág. 127-132

Se demuestran por inducción sobre z (naturales incluyendo el cero):

• A(1, z) = z + 2. Paso base: A(1, 0) = A(0, 1) = 1 + 1 = 2 = 0 + 2. Hipótesis: A(1, n) = n + 2. Paso inductivo: A(1, n+1) = A(0, A(1, n)) = A(0, n+2) = n + 2 + 1 = (n+1) + 2.
• A(2, z) = 2z + 3. Paso base: A(2, 0) = A(1, 1) = A(0, A(1, 0)) = A(0, A(0, 1)) = A(0, 2) = 3. Paso inductivo: A(2, n+1) = A(1, A(2, n)) = A(1, 2n + 3) = 2n + 3 + 2 = 2(n+1) + 3.
• A(3, z) = 2^(z+3) − 3. Paso base: A(3, 0) = A(2, 1) = 2·1 + 3 = 5 = 2^3 − 3. Paso inductivo: A(3, n+1) = A(2, A(3, n)) = A(2, 2^(n+3) − 3) = 2·(2^(n+3) − 3) + 3 = 2^(n+4) − 3 = 2^((n+1)+3) − 3.
• A(4, z) = 2^(2^(…)) − 3 (una torre de potencias de 2 con z + 2 términos, menos 3). Paso base: A(4, 0) = A(3, 1) = 2^4 − 3 = 16 − 3 = 13 = 2^2 − 3. Por inducción se obtiene la torre de exponentes.
• Ejemplos: A(4, 1) = 65533; A(4, 2) = … − 3 que tiene 19 729 dígitos.

De estas propiedades se desprende por qué la función de Ackermann crece muy rápido. Para valores superiores de m y n la función obtiene valores exponenciales de 2. Según la conferencia, A(4, 2) es mayor que el número de partículas del universo elevado a la potencia 200, y el resultado de A(5, 2) no se puede escribir, dado que no cabría en el Universo físico.

Ejercicios con ternas de Hoare (usando Ackermann) Pág. 134-135

• a) { x = 1 } w := A( x, y ) { w = y + 2 }. Por la regla de la asignación, la precondición es { A(x, y) = y + 2 }; como ya se demostró que A(1, z) = z + 2, de { x = 1 } se sigue { A(x, y) = y + 2 }, y la terna es válida (q.l.q.d.).
• a) { x = 2 } w := A( x, y ) { w = 2y + 3 }. Por la regla de la asignación, la precondición es { A(x, y) = 2y + 3 }; como ya se demostró que A(2, z) = 2z + 3, de { x = 2 } se sigue esa precondición, y la terna es válida (q.l.q.d.).

Otras propiedades: inducción sobre dos variables Pág. 136-138

Se demuestra que para x, y ≥ 0 se cumple y + 1 ≤ A( x, y ), aplicando inducción sobre x y, dentro, inducción sobre y:

• Paso base (x = 0): y + 1 ≤ A(0, y) = y + 1, cierto.
• Hipótesis de inducción (sobre x): y + 1 ≤ A(n, y) … (1).
• P. D. y + 1 ≤ A(n + 1, y) … (2), aplicando inducción sobre y (paso base y = 0: 1 ≤ A(n + 1, 0) = A(n, 1), que se sigue de (1); y paso inductivo usando las ecuaciones de Ackermann).

2 Puntos destacados / Lo que hay que saber

3 Actividades y tareas pendientes

No se indicaron tareas con fecha de entrega en esta clase.

El profesor mostró y explicó la función 91 de McCarthy, la inducción modificada y la función de Ackermann, y planteó los proyectos Funcion91JohnMcCarthy, Ackermann (Visual Studio y Haskell) y el documento Ackermann.doc como material de referencia.

4 Dudas que podrían examinar

5 Sitios o recursos para visitar

• Función 91 de McCarthy (Wikipedia) — definición, historia y la demostración clásica del teorema (dominio: wikipedia.org).
• Función de Ackermann (Wikipedia) — definición, historia y propiedades (dominio: wikipedia.org).
• Zohar Manna · Mathematical Theory of Computation — libro clásico que popularizó la función 91 como caso de prueba para la verificación formal de programas (dominio: google.com).
• Visual Studio — el entorno donde el profesor mostró los proyectos Funcion91JohnMcCarthy y Ackermann (dominio: visualstudio.microsoft.com).
• Búsqueda: función 91 de McCarthy y función de Ackermann — para contrastar definiciones y ver más ejemplos resueltos (dominio: google.com).

6 Glosario de términos

• Función 91 de McCarthy: función recursiva f(x) = x − 10 si x > 100 y f(x) = f(f(x + 11)) si x ≤ 100; vale 91 para todo entero x ≤ 100.
• Inducción simple: principio que demuestra el caso base P(k) y que P(n) implica P(n + 1).
• Inducción modificada (fuerte): principio que demuestra P(k) y que, si para n ≥ k se sigue P(n) cuando P(m) es verdadera para n < m < k, entonces P(n) vale para toda n ≥ k.
• Paso base: comprobación de que la proposición se cumple en el punto inicial de la inducción (p. ej., f(100) = 91).
• Paso inductivo: demostración de que, si la propiedad se cumple para un valor (o intervalo), se cumple para el siguiente.
• Hipótesis de inducción: suposición de que la propiedad ya está demostrada para ciertos valores (en la inducción fuerte, para P(m) con m en el intervalo), usada para probar el paso inductivo.
• Función de Ackermann: función doblemente recursiva A(m, n) (1928, Wilhelm Friedrich Ackermann) que crece muy rápido; A(1,z) = z + 2, A(2,z) = 2z + 3, A(3,z) = 2^(z+3) − 3, etc.
• Recursión doble: función que se llama a sí misma con dos argumentos de forma anidada.
• StackOverflowException: error de desbordamiento de pila; la conferencia lo menciona como consecuencia de valores muy grandes o recursión muy profunda en la función de Ackermann.
• Terna de Hoare: notación {P} C {Q} que relaciona precondición, código y poscondición.
• q.l.q.d.: "queda lo que quería demostrar" (QED); marca el fin de una demostración.

7 Mapa mental textual

• Programación Avanzada · Clase 7 (Nota 7)
  • Función 91 de John McCarthy (1970)
    • Definición: f(x) = x − 10 si x > 100; f(x) = f(f(x + 11)) si x ≤ 100
    • Resultado: f(x) = 91 para todo x ≤ 100; x − 10 para x > 100
    • John McCarthy (1927–2011): padre de la IA (Dartmouth 1956), Lisp, Premio Turing 1971
    • Proyecto Funcion91JohnMcCarthy (Visual Studio)
  • Inducción modificada (fuerte)
    • Paso base P(k) + paso inductivo usando P(m), n < m < k
    • Sirve cuando la recursión usa valores mayores (x + 11)
  • Demostración de la función 91
    • Paso base: f(100) = f(f(111)) = f(101) = 91
    • Caso a) x + 11 > 100: f(x) = f(x + 1) = 91
    • Caso b) x + 11 ≤ 100: f(x) = f(91) = 91
  • Función de Ackermann (1928)
    • Definición recursiva A(m, n); alternativa A(0,y)=y+1, A(x+1,0)=A(x,1), A(x+1,y+1)=A(x,A(x+1,y))
    • Propiedades: A(1,z)=z+2, A(2,z)=2z+3, A(3,z)=2^(z+3)−3, A(4,z)= torre de 2s − 3
    • Valores enormes: A(4,1)=65533; A(4,2) tiene 19 729 dígitos; > partículas del universo^200; A(5,2) no se puede escribir
    • Proyectos: Ackermann (Visual Studio, Haskell), Ackermann.doc
  • Aplicaciones
    • Ternas de Hoare: {x=1} w:=A(x,y) {w=y+2}; {x=2} w:=A(x,y) {w=2y+3}
    • Inducción sobre dos variables: y + 1 ≤ A(x, y)